package com.datastructure.string;

/**
 * @author: 临晖
 * @date: 2023/10/16
 * @description:
 */


import java.util.Arrays;

/**
 * 反转字符串中的单词
 */
public class Solution03 {


    /**
     * 给你一个字符串 s ，请你反转字符串中 单词 的顺序。
     * 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
     * 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
     * 注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
     *
     * @param s
     * @return
     */
    public static String reverseWords(String s) {
        char[] ans = s.toCharArray();
        int fast = 0;
        int slow = 0;
        //去除重复空格
        for (; fast < s.length(); fast++) {
            if (ans[fast] != ' ' || (slow > 0 && ans[fast] == ' ' && ans[slow - 1] != ' ')) {
                ans[slow] = ans[fast];
                slow++;
            }
        }


        //去除最后的空格
        if (ans[fast - 1] == ' ') {
            slow--;
        }
        //更换新的数组
        ans = Arrays.copyOf(ans, slow);
        //整体反转
        rever(ans, 0, ans.length - 1);
        //个体单词反转
        for (int i = 0, j = 0; i < ans.length; i++) {
            if (ans[i] == ' ') {
                rever(ans, j, i - 1);
                j = i + 1;
            } else if ((i + 1) == ans.length) {
                rever(ans, j, i);
            }
        }

        return new String(ans);
    }

    public static void rever(char[] ans, int m, int n) {
        while (m < n) {
            char temp = ans[m];
            ans[m] = ans[n];
            ans[n] = temp;
            m++;
            n--;
        }
    }


    public static void main(String[] args) {
        System.out.println(reverseWords("  hello world  "));
    }
}
